// Copyright (C) Kumo inc. and its affiliates.
// Author: Jeff.li lijippy@163.com
// All rights reserved.
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published
// by the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.
//
#pragma once
#include <pollux/common/hyperloglog/dense_hll.h>
#include <pollux/common/memory/hash_string_allocator.h>

namespace kumo::pollux::common::hll {
    /// HyperLogLog implementation using sparse storage layout.
    /// It uses 26-bit buckets and provides high accuracy for low cardinalities.
    /// Memory usage: 4 bytes for each observed bucket.
    class SparseHll {
    public:
        explicit SparseHll(HashStringAllocator *allocator)
            : entries_{StlAllocator<uint32_t>(allocator)} {
        }

        SparseHll(const char *serialized, HashStringAllocator *allocator);

        void setSoftMemoryLimit(uint32_t softMemoryLimit) {
            softNumEntriesLimit_ = softMemoryLimit / 4;
        }

        /// Return whether soft memory limit has been reached.
        bool overLimit() const {
            return entries_.size() >= softNumEntriesLimit_;
        }

        /// Returns true if soft memory limit has been reached. False, otherwise.
        bool insertHash(uint64_t hash);

        int64_t cardinality() const;

        /// Returns cardinality estimate from the specified serialized digest.
        static int64_t cardinality(const char *serialized);

        /// Serializes internal state using Presto SparseV2 format.
        void serialize(int8_t indexBitLength, char *output) const;

        static std::string serializeEmpty(int8_t indexBitLength);

        /// Returns true if 'input' has Presto SparseV2 format.
        static bool canDeserialize(const char *input);

        /// Returns the size of the serialized state without serialising.
        int32_t serializedSize() const;

        /// Merges the state of another instance into this one.
        void mergeWith(const SparseHll &other);

        /// Merges the state of another instance (in serialized form) into this one.
        void mergeWith(const char *serialized);

        /// Merges state into provided instance of DenseHll.
        void toDense(DenseHll &denseHll) const;

        /// Returns current memory usage.
        int32_t inMemorySize() const;

        // Clear accumulated state and release memory. Used to free up memory after
        // converting to dense layout.
        void reset() {
            entries_.clear();
            entries_.shrink_to_fit();
        }

        // For testing: sanity checks internal state.
        void verify() const;

    private:
        void mergeWith(size_t otherSize, const uint32_t *otherEntries);

        /// A list of observed buckets. Each entry is a 32 bit integer encoding 26-bit
        /// bucket and 6-bit value (number of zeros in the input hash after the bucket
        /// + 1).
        std::vector<uint32_t, StlAllocator<uint32_t> > entries_;

        /// Number of entries that can be stored before reaching soft memory limit.
        uint32_t softNumEntriesLimit_{0};
    };
} // namespace kumo::pollux::common::hll
